package common.t6038.minimizeResult;


/**
 * https://leetcode-cn.com/problems/minimize-result-by-adding-parentheses-to-expression/
 * 给你一个下标从 0 开始的字符串 expression ，格式为 "<num1>+<num2>" ，其中 <num1> 和 <num2> 表示正整数。
 * 请你向 expression 中添加一对括号，使得在添加之后， expression 仍然是一个有效的数学表达式，并且计算后可以得到 最小 可能值。左括号 必须 添加在 '+' 的左侧，而右括号必须添加在 '+' 的右侧。
 * 返回添加一对括号后形成的表达式 expression ，且满足 expression 计算得到 最小 可能值。如果存在多个答案都能产生相同结果，返回任意一个答案。
 *
 * 想法：
 * 暴力
 *
 * 执行用时：8 ms, 在所有 Java 提交中击败了100%的用户
 * 内存消耗：40.3 MB, 在所有 Java 提交中击败了100%的用户
 * 此题为周赛题目，击败100%是无意义的数据
 */
public class Solution {

    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(solution.minimizeResult("247+38"));
        System.out.println(solution.minimizeResult("12+34"));
    }

    /**
     * 添加括号后获得的最小数字
     */
    public String minimizeResult(String expression) {
        // 获取两个加数
        String[] nums = expression.split("\\+");

        // 12+34 可以变为 1(2+3)4 变化后的式子里，a = 1，b = (2+3)，c = 4，如果变化后的式子为 (12+3)4 变化后的式子里，a = 1，b = (12+3)，c = 4
        int res = Integer.MAX_VALUE;
        String resStr = "(" + expression + ")";
        // i用来分割第一个加数，j用来分割第二个加数
        for (int i = 0; i <= nums[0].length() - 1; i++) {
            for (int j = 1; j <= nums[1].length(); j++) {
                String num1 = nums[0].substring(0, i);
                String num2 = nums[0].substring(i);
                String num3 = nums[1].substring(0, j);
                String num4 = nums[1].substring(j);

                int a = 1;
                if (num1.length() != 0) {
                    a = Integer.parseInt(num1);
                }
                int b = Integer.parseInt(num2) + Integer.parseInt(num3);
                int c = 1;
                if (num4.length() != 0) {
                    c = Integer.parseInt(num4);
                }

                int num = a * b * c;
                if (num < res) {
                    res = num;
                    resStr = num1 + "(" + num2 + "+" + num3 + ")" + num4;
                }
            }
        }
        return resStr;
    }
}
